{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Faulty Sensor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: badSensor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有缺陷的传感器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>实验室里正在进行一项实验。为了确保数据的准确性，同时使用 <strong>两个</strong> 传感器来采集数据。您将获得2个数组 <code>sensor1</code> and <code>sensor2</code>，其中 <code>sensor1[i]</code>&nbsp;和&nbsp;<code>sensor2[i]</code>&nbsp;分别是两个传感器对<span style=\"\">第 <code>i</code> 个</span>数据点采集到的数据。</p>\n",
    "\n",
    "<p>但是，这种类型的传感器有可能存在缺陷，它会导致 <strong>某一个</strong> 数据点采集的数据（掉落值）被丢弃。</p>\n",
    "\n",
    "<p>数据被丢弃后，所有在其右侧的数据点采集的数据，都会被向左移动一个位置，最后一个数据点采集的数据会被一些随机值替换。可以保证此随机值不等于掉落值。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举个例子, 如果正确的数据是&nbsp;<code>[1,2,<em><strong>3</strong></em>,4,5]</code>&nbsp;，&nbsp;此时 <code>3</code> 被丢弃了, 传感器会返回&nbsp;<code>[1,2,4,5,<em><strong>7</strong></em>]</code> (最后的位置可以是任何值, 不仅仅是&nbsp;<code>7</code>).</li>\n",
    "</ul>\n",
    "\n",
    "<p>可以确定的是，<strong>最多有一个</strong> 传感器有缺陷。请返回这个有缺陷的传感器的编号 （<code>1</code> 或 <code>2</code>）。如果任一传感器 <strong>没有缺陷</strong> ，或者 <strong>无法</strong> 确定有缺陷的传感器，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sensor1 = [2,3,4,5], sensor2 = [2,1,3,4]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>传感器 2 返回了所有正确的数据.\n",
    "传感器2对第二个数据点采集的数据，被传感器1丢弃了，传感器1返回的最后一个数据被替换为 5 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sensor1 = [2,2,2,2,2], sensor2 = [2,2,2,2,5]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>无法判定哪个传感器是有缺陷的。\n",
    "假设任一传感器丢弃的数据是最后一位，那么，另一个传感器就能给出与之对应的输出。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>sensor1 = [2,3,2,2,3,2], sensor2 = [2,3,2,3,2,7]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>传感器 1 返回了所有正确的数据.\n",
    "传感器 1 对第四个数据点的采集数据，被传感器2丢失了, 传感器 2 返回的最后一个数据被替换为 7 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>sensor1.length == sensor2.length</code></li>\n",
    "\t<li><code>1 &lt;= sensor1.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= sensor1[i], sensor2[i] &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [faulty-sensor](https://leetcode.cn/problems/faulty-sensor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [faulty-sensor](https://leetcode.cn/problems/faulty-sensor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,4,5]\\n[2,1,3,4]', '[2,2,2,2,2]\\n[2,2,2,2,5]', '[2,3,2,2,3,2]\\n[2,3,2,3,2,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        n = len(sensor1)\n",
    "        diff_idx = -1\n",
    "        for i in range(n):\n",
    "            if sensor1[i] != sensor2[i]:\n",
    "                diff_idx = i \n",
    "                break \n",
    "        if diff_idx == -1:\n",
    "            return -1\n",
    "        if sensor1[diff_idx + 1:] == sensor2[diff_idx: n - 1] and sensor1[diff_idx: n - 1] == sensor2[diff_idx + 1:]:\n",
    "            return -1\n",
    "        if sensor1[diff_idx + 1:] == sensor2[diff_idx: n - 1]:\n",
    "            return 2\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        n = len(sensor1)\n",
    "        i = 0\n",
    "        while i < n and sensor1[i] == sensor2[i]:\n",
    "            i += 1\n",
    "        if i >= n-1:\n",
    "            return -1\n",
    "        res1 = sensor1[i:-1] == sensor2[i+1:]\n",
    "        res2 = sensor2[i:-1] == sensor1[i+1:]\n",
    "        if res1 and not res2:\n",
    "            return 1\n",
    "        elif not res1 and res2:\n",
    "            return 2\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\r\n",
    "        n = len(sensor1)\r\n",
    "\r\n",
    "        i = 0  \r\n",
    "        while i < n:\r\n",
    "            if sensor1[i] != sensor2[i]:\r\n",
    "                break       #从左往右第一次不同的位置\r\n",
    "            i += 1\r\n",
    "\r\n",
    "        if n - 1 <= i:      #如果只是最后一位不同，或者完全相同\r\n",
    "            return -1       #无法判断\r\n",
    "\r\n",
    "        lose = -1\r\n",
    "        \r\n",
    "        if sensor1[i+1: ] == sensor2[i:-1] and sensor1[i] != sensor2[-1]:\r\n",
    "            lose = 2\r\n",
    "        if sensor2[i+1: ] == sensor1[i:-1] and sensor2[i] != sensor1[-1]:\r\n",
    "            if lose == 2:\r\n",
    "                lose = -1       #2个都成立，则判断不出到底是哪个\r\n",
    "            else:\r\n",
    "                lose = 1\r\n",
    "        return lose"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Python3 模拟\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        slen = len(sensor1)\n",
    "        for i in range(slen):\n",
    "            if sensor1[i] != sensor2[i]:\n",
    "                a = sensor1[i+1:]\n",
    "                b = sensor2[i:slen-1]\n",
    "                c = sensor1[i:slen -1]\n",
    "                d = sensor2[i+1:]\n",
    "                if a == b and c != d:\n",
    "                    return 2\n",
    "                if c == d and a != b:\n",
    "                    return 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        n = len(sensor1)\n",
    "        if sensor1 == sensor2:\n",
    "            return -1\n",
    "        for i in range(n):\n",
    "            if sensor1[i] != sensor2[i]:\n",
    "                break\n",
    "                \n",
    "        if sensor1[i:-1] == sensor2[i + 1:] and sensor2[i:-1] == sensor1[i + 1:]:\n",
    "            return -1\n",
    "        if sensor1[i + 1:] == sensor2[i:-1]:\n",
    "            return 2\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        n = len(sensor1)\n",
    "        diff_idx = -1\n",
    "        for i in range(n):\n",
    "            if sensor1[i] != sensor2[i]:\n",
    "                diff_idx = i \n",
    "                break \n",
    "        if diff_idx == -1 or diff_idx == n - 1:\n",
    "            return -1\n",
    "        if sensor1[diff_idx + 1:] == sensor2[diff_idx: n - 1] and sensor1[diff_idx: n - 1] == sensor2[diff_idx + 1:]:\n",
    "            return -1\n",
    "        if sensor1[diff_idx + 1:] == sensor2[diff_idx: n - 1]:\n",
    "            return 2\n",
    "        return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        for i in range(len(sensor1)):\n",
    "            if sensor1[i] != sensor2[i]:\n",
    "                break\n",
    "        if i == len(sensor1) - 1:\n",
    "            return -1\n",
    "        if sensor1[i: -1] == sensor2[i + 1:] and sensor1[i + 1:] == sensor2[i: -1]:\n",
    "            return -1\n",
    "        return 1 if sensor1[i:-1] == sensor2[i + 1:] else 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        slen = len(sensor1)\n",
    "        \n",
    "        for i in range(slen):\n",
    "            # 寻找第一个不匹配的数据点\n",
    "            if sensor1[i] != sensor2[i]:\n",
    "                # 取出两个传感器在不匹配点之后的数据，并去掉最后一个数据点\n",
    "                a = sensor1[i+1:]\n",
    "                b = sensor2[i:slen-1]\n",
    "                c = sensor1[i:slen-1]\n",
    "                d = sensor2[i+1:]\n",
    "                \n",
    "                # 判断哪个传感器有缺陷\n",
    "                if a == b and c != d:\n",
    "                    return 2\n",
    "                if c == d and a != b:\n",
    "                    return 1\n",
    "                    \n",
    "        return -1  # 无法确定哪个传感器有缺陷，或者都没有缺陷\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        n = len(sensor1)\n",
    "        pre = 0\n",
    "        while pre < n and sensor1[pre] == sensor2[pre]:\n",
    "            pre += 1\n",
    "        if pre >= n-1:\n",
    "            return -1\n",
    "        \n",
    "        a = sensor1[pre:]\n",
    "        b = sensor2[pre:]\n",
    "        eq1 = (str(a[1:]) == str(b[:-1]))\n",
    "        eq2 = (str(a[:-1]) == str(b[1:]))\n",
    "        if eq1 and eq2:\n",
    "            return -1\n",
    "        elif eq1:\n",
    "            return 2\n",
    "        elif eq2:\n",
    "            return 1\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... 48 ms ... 12 % ... 16.1 MB ... 0 %\n",
    "        #  time: O(n^2)\n",
    "        # space: O(n)\n",
    "        \n",
    "        def match(good, bad):\n",
    "            for i, num in enumerate(good):\n",
    "                if num != bad[-1] and good[:i] + good[i+1:] == bad[:-1]:\n",
    "                    return 1\n",
    "            return 0\n",
    "        \n",
    "        good1bad2 = match(sensor1, sensor2)\n",
    "        good2bad1 = match(sensor2, sensor1)\n",
    "        if good1bad2 + good2bad1 == 1:\n",
    "            return 2 if good1bad2 else 1\n",
    "        return -1\n",
    "        \n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
